package test;

import gnu.trove.map.TCharObjectMap;
import gnu.trove.map.hash.TCharObjectHashMap;
import gnu.trove.set.TCharSet;
import gnu.trove.set.hash.TCharHashSet;
import java.util.HashMap;
import java.util.Map;

/**
 * Implementation of <code>String</code> similarity measures with basis on
 * Keyboard proximity. 
 * <p>
 * The keyboard is assumed to have a QWERTY layout, and we 
 * also make a distinction between keys on the same row of the keyboard
 * (which therefore should be 'more similar') and adjacent keys.
 * <p>
 * A large percentage of spelling mistakes are typographical errors, mainly
 * due to keyboard typing slips (e.g. Jack becomes Hack since
 * h and j are next to each other on the keyboard). Handling these errors
 * is therefore of special importance.
 * 
 * @author Bruno Martins
 *
 */
public class KeyboardProximity {

    /** Associates keys with a <code>Map</code> of adjacent keys in the same row of the keyboard. */
    private static TCharObjectMap<TCharSet> firstChars;
    /** Associates keys with a <code>Map</code> of adjacent keys but at diferent rows of the keyboard. */
    private static TCharObjectMap<TCharSet> secondChars;
    /** The single instance of this class. */
    private static final KeyboardProximity theInstance = new KeyboardProximity();

    /**
     *  Sole constructor, private because this is a Singleton class. 
     */
    private KeyboardProximity() {
        firstChars = new TCharObjectHashMap<TCharSet>();
        secondChars = new TCharObjectHashMap<TCharSet>();
        TCharSet temp;

        // q
        temp = new TCharHashSet();
        temp.add('w');
        firstChars.put('q', temp);
        temp = new TCharHashSet();
        temp.add('a');
        temp.add('1');
        firstChars.put('q', temp);

        // w
        temp = new TCharHashSet();
        temp.add('q');
        temp.add('e');
        firstChars.put('w', temp);
        temp = new TCharHashSet();
        temp.add('2');
        temp.add('s');
        temp.add('a');
        temp.add('d');
        secondChars.put('w', temp);

        // e
        temp = new TCharHashSet();
        temp.add('w');
        temp.add('r');
        firstChars.put('e', temp);
        temp = new TCharHashSet();
        temp.add('3');
        temp.add('d');
        temp.add('s');
        temp.add('f');
        secondChars.put('e', temp);

        // r
        temp = new TCharHashSet();
        temp.add('e');
        temp.add('t');
        firstChars.put('r', temp);
        temp = new TCharHashSet();
        temp.add('4');
        temp.add('f');
        temp.add('d');
        temp.add('g');
        secondChars.put('r', temp);

        // t
        temp = new TCharHashSet();
        temp.add('r');
        temp.add('y');
        firstChars.put('t', temp);
        temp = new TCharHashSet();
        temp.add('5');
        temp.add('g');
        temp.add('f');
        temp.add('h');
        secondChars.put('t', temp);

        // y
        temp = new TCharHashSet();
        temp.add('t');
        temp.add('u');
        firstChars.put('y', temp);
        temp = new TCharHashSet();
        temp.add('6');
        temp.add('h');
        temp.add('g');
        temp.add('j');
        secondChars.put('y', temp);

        // u
        temp = new TCharHashSet();
        temp.add('y');
        temp.add('i');
        firstChars.put('u', temp);
        temp = new TCharHashSet();
        temp.add('7');
        temp.add('j');
        temp.add('h');
        temp.add('k');
        secondChars.put('u', temp);

        // i
        temp = new TCharHashSet();
        temp.add('u');
        temp.add('o');
        firstChars.put('i', temp);
        temp = new TCharHashSet();
        temp.add('8');
        temp.add('k');
        temp.add('j');
        temp.add('l');
        secondChars.put('i', temp);

        // o
        temp = new TCharHashSet();
        temp.add('i');
        temp.add('p');
        firstChars.put('o', temp);
        temp = new TCharHashSet();
        temp.add('9');
        temp.add('l');
        temp.add('k');
        temp.add('ç');
        secondChars.put('o', temp);

        // p
        temp = new TCharHashSet();
        temp.add('o');
        firstChars.put('p', temp);
        temp = new TCharHashSet();
        temp.add('0');
        temp.add('ç');
        temp.add('l');
        temp.add('º');
        secondChars.put('p', temp);

        // z
        temp = new TCharHashSet();
        temp.add('<');
        firstChars.put('z', temp);
        temp = new TCharHashSet();
        temp.add('a');
        temp.add('s');
        secondChars.put('z', temp);

        // x
        temp = new TCharHashSet();
        temp.add('z');
        temp.add('c');
        firstChars.put('x', temp);
        temp = new TCharHashSet();
        temp.add('a');
        temp.add('s');
        temp.add('d');
        secondChars.put('x', temp);

        // c
        temp = new TCharHashSet();
        temp.add('x');
        temp.add('v');
        firstChars.put('c', temp);
        temp = new TCharHashSet();
        temp.add('s');
        temp.add('d');
        temp.add('f');
        secondChars.put('c', temp);

        // v
        temp = new TCharHashSet();
        temp.add('c');
        temp.add('b');
        firstChars.put('v', temp);
        temp = new TCharHashSet();
        temp.add('d');
        temp.add('f');
        temp.add('g');
        secondChars.put('v', temp);

        // b
        temp = new TCharHashSet();
        temp.add('v');
        temp.add('n');
        firstChars.put('b', temp);
        temp = new TCharHashSet();
        temp.add('f');
        temp.add('g');
        temp.add('h');
        secondChars.put('b', temp);

        // n
        temp = new TCharHashSet();
        temp.add('b');
        temp.add('m');
        firstChars.put('n', temp);
        temp = new TCharHashSet();
        temp.add('g');
        temp.add('h');
        temp.add('j');
        secondChars.put('n', temp);

        // m
        temp = new TCharHashSet();
        temp.add('n');
        temp.add(',');
        firstChars.put('m', temp);
        temp = new TCharHashSet();
        temp.add('h');
        temp.add('j');
        temp.add('k');
        secondChars.put('m', temp);

        // a
        temp = new TCharHashSet();
        temp.add('s');
        firstChars.put('a', temp);
        temp = new TCharHashSet();
        temp.add('q');
        temp.add('w');
        temp.add('z');
        temp.add('x');
        secondChars.put('a', temp);

        // s
        temp = new TCharHashSet();
        temp.add('a');
        temp.add('d');
        firstChars.put('s', temp);
        temp = new TCharHashSet();
        temp.add('q');
        temp.add('w');
        temp.add('e');
        temp.add('z');
        temp.add('x');
        temp.add('c');
        secondChars.put('s', temp);

        // d
        temp = new TCharHashSet();
        temp.add('s');
        temp.add('f');
        firstChars.put('d', temp);
        temp = new TCharHashSet();
        temp.add('w');
        temp.add('e');
        temp.add('r');
        temp.add('x');
        temp.add('c');
        temp.add('v');
        secondChars.put('d', temp);

        // f
        temp = new TCharHashSet();
        temp.add('d');
        temp.add('g');
        firstChars.put('f', temp);
        temp = new TCharHashSet();
        temp.add('e');
        temp.add('r');
        temp.add('t');
        temp.add('c');
        temp.add('v');
        temp.add('b');
        secondChars.put('f', temp);

        // g
        temp = new TCharHashSet();
        temp.add('f');
        temp.add('h');
        firstChars.put('g', temp);
        temp = new TCharHashSet();
        temp.add('r');
        temp.add('t');
        temp.add('y');
        temp.add('v');
        temp.add('b');
        temp.add('n');
        secondChars.put('g', temp);

        // h
        temp = new TCharHashSet();
        temp.add('g');
        temp.add('j');
        firstChars.put('h', temp);
        temp = new TCharHashSet();
        temp.add('t');
        temp.add('y');
        temp.add('u');
        temp.add('b');
        temp.add('n');
        temp.add('m');
        secondChars.put('h', temp);

        // j
        temp = new TCharHashSet();
        temp.add('h');
        temp.add('k');
        firstChars.put('j', temp);
        temp = new TCharHashSet();
        temp.add('y');
        temp.add('u');
        temp.add('i');
        temp.add('n');
        temp.add('m');
        temp.add(',');
        secondChars.put('j', temp);

        // k
        temp = new TCharHashSet();
        temp.add('j');
        temp.add('l');
        firstChars.put('k', temp);
        temp = new TCharHashSet();
        temp.add('u');
        temp.add('i');
        temp.add('o');
        temp.add('m');
        temp.add(',');
        temp.add('.');
        secondChars.put('k', temp);

        // l
        temp = new TCharHashSet();
        temp.add('k');
//		temp.add('ç');
        temp.add('ñ');//Spanish keyboard
        firstChars.put('l', temp);
        temp = new TCharHashSet();
        temp.add('i');
        temp.add('o');
        temp.add('p');
        temp.add(',');
        temp.add('.');
        temp.add('-');
        secondChars.put('l', temp);
    }

    /**
     * Return the single instance of this class.
     *
     * @return An instance of <code>KeyboardProximity</code>.
     */
    public static KeyboardProximity getInstance() {
        return theInstance;
    }

    /**
     *  Check if two characters are adjacent in the same row of the keyboard.
     *
     *@param       ch1 A character.
     *@param       ch2 Another character.
     *@return        true if the characters are adjacent in the same row of the keyboard and false otherwise.
     */
    public static boolean isSameRow(char ch1, char ch2) {
        TCharSet auxh = firstChars.get(ch1);
        if (auxh == null) {
            return false;
        }
        return (auxh.contains(ch2));
    }

    /**
     *  Check if two characters are adjacent in the keyboard.
     *
     *@param       ch1 A character.
     *@param       ch2 Another character.
     *@return        true if the characters are adjacent in the keyboard and false otherwise.
     */
    public static boolean isNear(char ch1, char ch2) {
        if (isSameRow(ch1, ch2)) {
            return true;
        }
        TCharSet auxh = secondChars.get(ch1);
        if (auxh == null) {
            return false;
        }
        return (auxh.contains(ch2));
    }

    /**
     *  Check if two <code>String</code> objects differ in only a given number of characters adjacent in the same row of the keyboard.
     *
     *@param       s1 A <code>String</code>.
     *@param       s2 Another <code>String</code>.
     *@param       n the number of diferent characters. 
     *@return        true if the strings differ in only a given number of characters adjacent in the same row of the keyboard and false otherwise.
     */
    public static boolean stringsSameRow(String s1, String s2, int n) {
        int c = s1.length();
        if (s2.length() != c) {
            return false;
        }
        for (int i = 0, j = 0; i < c && j < n; i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            if (c1 == c2) {
                continue;
            }
            if (!isSameRow(c1, c2)) {
                return false;
            } else {
                j++;
            }
        }
        return true;
    }

    /**
     *  Check if two <code>String</code> objects differ in only one character adjacent in the same row of the keyboard.
     *
     *@param       s1 A <code>String</code>.
     *@param       s2 Another <code>String</code>.
     *@return        true if the strings differ in only one character adjacent in the same row of the keyboard and false otherwise.
     */
    public static boolean stringsSameRow(String s1, String s2) {
        return stringsSameRow(s1, s2, 1);
    }

    /**
     *  Check if two <code>String</code> objects differ in only a given number of characters adjacent in the keyboard.
     *
     *@param       s1 A <code>String</code>.
     *@param       s2 Another <code>String</code>.
     *@param       n the maximum number of diferent characters. 
     *@return        true if the strings differ in only a given number of characters adjacent in the keyboard and false otherwise.
     */
    public static boolean stringsNear(String s1, String s2, int n) {
        int c = s1.length();
        if (s2.length() != c) {
            return false;
        }
        for (int i = 0, j = 0; i < c && j < n; i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            if (c1 == c2) {
                continue;
            }
            if (!isNear(c1, c2)) {
                return false;
            } else {
                j++;
            }
        }
        return true;
    }

    /**
     *  Check if two <code>String</code> objects differ in only one character adjacent in the keyboard.
     *
     *@param       s1 A <code>String</code>.
     *@param       s2 Another <code>String</code>.
     *@return        true if the strings differ in only one character adjacent in the keyboard and false otherwise.
     */
    public static boolean stringsNear(String s1, String s2) {
        return stringsNear(s1, s2, 1);
    }

    /**
     *  Returns the similarity between two <code>String</code> objects in terms of the number of 
     *  different characters that are adjacent in the keyboard.
     *
     *@param       s1 A <code>String</code>.
     *@param       s2 Another <code>String</code>.
     *@return        -1 if the strings differ in more than adjacent characters, 0 if the strings are equal
     *					  and the number of different characters otherwise.
     */
    public static int similarityStringsNear(String s1, String s2) {
        int count = 0;
        int c = s1.length();
        if (s2.length() != c) {
            return -1;
        }
        for (int i = 0; i < c; i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            if (c1 == c2) {
                continue;
            }
            if (!isNear(c1, c2)) {
                return -1;
            } else {
                count++;
            }
        }
        return count;
    }

    /**
     *  Returns the similarity between two <code>String</code> objects in terms of the number of 
     *  different characters that are adjacent in the same row of the keyboard.
     *
     *@param       s1 A <code>String</code>.
     *@param       s2 Another <code>String</code>.
     *@return        -1 if the strings differ in more than adjacent characters, 0 if the strings are equal
     *					  and the number of different characters otherwise.
     */
    public static int similarityStringsSameRow(String s1, String s2) {
        int count = 0;
        int c = s1.length();
        if (s2.length() != c) {
            return -1;
        }
        for (int i = 0; i < c; i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            if (c1 == c2) {
                continue;
            }
            if (!isSameRow(c1, c2)) {
                return -1;
            } else {
                count++;
            }
        }
        return count;
    }
}